# 作业  -递归

# 以下题目用递归方式实现
# 1. 计算1+2+3 ....+99+100
# 2. 求n的阶乘（n!）  (课上已讲过)
# 3. 一个人去买汽水。1块钱一瓶，3个瓶盖换一瓶汽水，两个空瓶换一瓶汽水。问：20块钱一共可以喝到多少瓶汽水。
# 4. 输出斐波拉切数列（1,1,2,3,5,8,13,21, ...）
# 5. 楼梯有N阶，上楼可以一步一阶，也可以一步两阶。
# 问：有多少种不同的走法。
# 提示：设n阶台阶的走法数为f(n)。如果只有1个台阶，走法有1种（一步上1个台阶），即f(1)=1；如果有2个台阶，走法有2种（一种是上1阶，再上1阶，另一种是一步上2阶），即f(2)=2；如果有3个台阶，走法有4种（一种每次1阶，共一种；另一种是2+1，共两种；第三种是3，共1种），即f(3)=4；
# 当有n个台阶（n>3）时，我们缩小问题规模，可以这样想：最后是一步上1个台阶的话，之前上了n-1个台阶，走法为f(n-1)种，而最后是一步上2个台阶的话，之前上了n-2个台阶，走法为f(n-2)种，故而f(n)=f(n-1)+f(n-2)。